#ifndef __GLF_MEM_FREELISTALLOCATOR_H_INCLUDED__
#define __GLF_MEM_FREELISTALLOCATOR_H_INCLUDED__

#include <glf/core/inlines.h>
#include <glf/core/atomic.h>
#include <glf/core/thread.h>

void* GlfAlloc(size_t);
void* GlfAlloc(size_t, glf::MemHint hint);
void  GlfFree(void* ptr);

namespace glf {

class FreelistAllocator
{
public:

	FreelistAllocator(size_t allocationSize)
		: m_BlockSize(allocationSize)
		, m_Head(0)
	{
	}

	~FreelistAllocator()
	{
		Clear();
	}

	void* Allocate(size_t size)
	{
		// *** NOTE: If you hit this assert, you need to increase the maximum 
		//           block size (the value passed to the constructor). System using
		//           freelist allocator will usually provide config #define to set
		//           this value.
		GLF_ASSERT(size <= m_BlockSize);

		void* p = Pop();
		if(p)
		{
			return p;
		}

		return GlfAlloc(m_BlockSize);
	}

	void Deallocate(void* p)
	{
		Push(p);
	}

	void Clear()
	{
		void* p;
		do
		{
			p = Pop();
			GlfFree(p);
		} 
		while(p);
	}

private:

	FreelistAllocator();

	void* Pop()
	{
		GLF_ASSERT(sizeof(size_t) == sizeof(void*));

		if(m_Head == 0) return 0;

		void* oldHead = m_Head;
		for(;;)
		{
			size_t* previous = (size_t*)oldHead;

			void* newHead = AtomicCompareAndSwap(m_Head, (void*)*previous, oldHead);

			if(oldHead == newHead)
			{
				break;
			}
			else
			{
				Thread::Sleep(0);
				oldHead = newHead;
			}
		}

		return oldHead;
	}

	void Push(void* p)
	{
		GLF_ASSERT(sizeof(size_t) ==  sizeof(void*));

		size_t* previous = (size_t*)p;
		void* oldHead = m_Head;
		for(;;)
		{
			*previous = (size_t)oldHead;
			void* newHead = AtomicCompareAndSwap(m_Head, p, oldHead);
			
			if(oldHead == newHead)
			{
				break;
			}
			else
			{
				Thread::Sleep(0);
				oldHead = newHead;
			}
		}
	}

	size_t m_BlockSize;
	void* m_Head;

};

} // end namespace glf

#endif // __GLF_MEM_FREELISTALLOCATOR_H_INCLUDED__
